#include "clib_container_double_linked_list.h"

struct clib_container_double_linked_list_node {
    void *data;
    struct clib_container_double_linked_list_node *next;
    struct clib_container_double_linked_list_node *prev;
};


struct clib_container_double_linked_list {
    size_t size;
    struct clib_container_double_linked_list_node *head;
    struct clib_container_double_linked_list_node *tail;

    void *(*mem_malloc_func)(size_t size);

    void (*mem_free_func)(void *block);

    void *(*mem_copy_func)(void *target, const void *src, size_t size);
};


int clib_container_double_linked_list_create_with_conf(struct clib_container_double_linked_list_conf *conf,
                                                       struct clib_container_double_linked_list **out) {
    struct clib_container_double_linked_list *list = conf->mem_malloc_func(
            sizeof(struct clib_container_double_linked_list));
    if (!list) {
        return CLIB_RES_MEMORY_ERROR;
    }
    list->mem_malloc_func = conf->mem_malloc_func;
    list->mem_free_func = conf->mem_free_func;
    list->mem_copy_func = conf->mem_copy_func;
    *out = list;
    return CLIB_RES_OK;
}

static void *
unlink_node(struct clib_container_double_linked_list *list,
            struct clib_container_double_linked_list_node *node) {
    void *data = node->data;
    if (node->prev != NULL)
        node->prev->next = node->next;

    if (node->prev == NULL)
        list->head = node->next;

    if (node->next == NULL)
        list->tail = node->prev;

    if (node->next != NULL)
        node->next->prev = node->prev;

    list->mem_free_func(node);
    list->size--;
    return data;
}

static int unlink_all(struct clib_container_double_linked_list *list, void **out) {
    if (list->size == 0) {
        return 0;
    }
    struct clib_container_double_linked_list_node *node = list->head;
    int remove_index = 0;
    while (node) {
        if (out != NULL) {
            out[remove_index] = node;
        }
        remove_index += 1;
        struct clib_container_double_linked_list_node *tmp = node->next;
        unlink_node(list, node);
        node = tmp;
    }
    return remove_index;
}

int clib_container_double_linked_list_remove_all(struct clib_container_double_linked_list *list, void **out) {
    int unlink_num = unlink_all(list, out);
    list->head = NULL;
    list->tail = NULL;
    return unlink_num;
}

void clib_container_double_linked_list_destroy(struct clib_container_double_linked_list *list) {
    if (list->size > 0) {
        clib_container_double_linked_list_remove_all(list, NULL);
    }
    list->mem_free_func(list);
}

int clib_container_double_linked_list_add_first(struct clib_container_double_linked_list *list, void *element) {
    struct clib_container_double_linked_list_node *node = list->mem_malloc_func(
            sizeof(struct clib_container_double_linked_list));
    if (node == NULL) {
        return CLIB_RES_MEMORY_ERROR;
    }
    node->data = element;

    if (list->size == 0) {
        list->head = node;
        list->tail = node;
    } else {
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->size++;
    return CLIB_RES_OK;
}

int clib_container_double_linked_list_add_last(struct clib_container_double_linked_list *list, void *element) {
    struct clib_container_double_linked_list_node *node = list->mem_malloc_func(
            sizeof(struct clib_container_double_linked_list_node));

    if (node == NULL) {
        return CLIB_RES_MEMORY_ERROR;
    }
    node->data = element;
    if (list->size == 0) {
        list->head = node;
        list->tail = node;
    } else {
        node->prev = list->tail;
        list->tail->next = node;
        list->tail = node;
    }
    list->size++;
    return CLIB_RES_OK;
}

int clib_container_double_linked_list_add(struct clib_container_double_linked_list *list, void *element) {
    return clib_container_double_linked_list_add_last(list, element);
}

static int get_node_index(struct clib_container_double_linked_list *list, size_t index,
                          struct clib_container_double_linked_list_node **out) {
    if (!list || index >= list->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    size_t i;
    struct clib_container_double_linked_list_node *node = NULL;
    if (index < list->size / 2) {
        node = list->head;
        for (i = 0; i < index; i++)
            node = node->next;
    } else {
        node = list->tail;
        for (i = list->size - 1; i > index; i--)
            node = node->prev;
    }
    *out = node;
    return CLIB_RES_OK;
}

static void link_behind(struct clib_container_double_linked_list_node *const base,
                        struct clib_container_double_linked_list_node *ins) {
    if (ins->next != NULL)
        ins->next->prev = ins->prev;

    if (ins->prev != NULL)
        ins->prev->next = ins->next;

    if (base->prev == NULL) {
        ins->prev = NULL;
        ins->next = base;
        base->prev = ins;
    } else {
        ins->prev = base->prev;
        ins->prev->next = ins;
        ins->next = base;
        base->prev = ins;
    }
}

int clib_container_double_linked_list_add_with_index(struct clib_container_double_linked_list *list, void *element,
                                                     size_t index) {
    struct clib_container_double_linked_list_node *base;
    int code = get_node_index(list, index, &base);
    if (code != CLIB_RES_OK) {
        return code;
    }
    struct clib_container_double_linked_list_node *new = list->mem_malloc_func(
            sizeof(struct clib_container_double_linked_list_node));

    if (!new) {
        return CLIB_RES_MEMORY_ERROR;
    }
    new->data = element;
    link_behind(base, new);

    if (index == 0) {
        list->head = new;
    }
    list->size++;
    return CLIB_RES_OK;
}

static bool
link_all_externally(struct clib_container_double_linked_list *list, struct clib_container_double_linked_list_node **h,
                    struct clib_container_double_linked_list_node **t) {
    struct clib_container_double_linked_list_node *insert = list->head;

    size_t i;
    for (i = 0; i < list->size; i++) {
        struct clib_container_double_linked_list_node *new = list->mem_malloc_func(
                sizeof(struct clib_container_double_linked_list_node));
        if (!new) {
            while (*h) {
                struct clib_container_double_linked_list_node *tmp = (*h)->next;
                list->mem_free_func(*h);
                *h = tmp;
            }
            return false;
        }
        new->data = insert->data;

        if (!*h) {
            *h = new;
            *t = new;
        } else {
            (*t)->next = new;
            new->prev = *t;
            *t = new;
        }

        insert = insert->next;
    }
    return true;
}

static int
add_all_to_empty(struct clib_container_double_linked_list *list1, struct clib_container_double_linked_list *list2) {
    if (list2->size == 0) {
        return CLIB_RES_OK;
    }
    struct clib_container_double_linked_list_node *head = NULL;
    struct clib_container_double_linked_list_node *tail = NULL;
    if (!link_all_externally(list2, &head, &tail)) {
        return CLIB_RES_MEMORY_ERROR;
    }
    list1->head = head;
    list1->tail = tail;
    list1->size = list2->size;
    return CLIB_RES_OK;
}

int clib_container_double_linked_list_add_all_with_index(struct clib_container_double_linked_list *list1,
                                                         struct clib_container_double_linked_list *list2,
                                                         size_t index) {
    if (list2->size == 0) {
        return CLIB_RES_OK;
    }
    if (index > list1->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    struct clib_container_double_linked_list_node *head = NULL;
    struct clib_container_double_linked_list_node *tail = NULL;

    if (!link_all_externally(list2, &head, &tail)) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    struct clib_container_double_linked_list_node *end = NULL;
    get_node_index(list1, index, &end);

    struct clib_container_double_linked_list_node *base = NULL;
    if (end) {
        base = end->prev;
    } else {
        get_node_index(list1, index - 1, &base);
    }
    if (!end) {
        list1->tail->next = head;
        head->prev = list1->tail;
        list1->tail = tail;
    } else if (!base) {
        list1->head->prev = tail;
        tail->next = list1->head;
        list1->head = head;
    } else {
        head->prev = base;
        base->next = head;
        tail->next = end;
        end->prev = tail;
    }

    list1->size += list2->size;

    return CLIB_RES_OK;
}

int clib_container_double_linked_list_add_all(struct clib_container_double_linked_list *list1,
                                              struct clib_container_double_linked_list *list2) {
    if (list1->size == 0) {
        return add_all_to_empty(list1, list2);
    }
    return clib_container_double_linked_list_add_all_with_index(list1, list2, list1->size);
}

static struct clib_container_double_linked_list_node *
get_node(struct clib_container_double_linked_list *list, void *element) {
    struct clib_container_double_linked_list_node *node = list->head;
    while (node) {
        if (node->data == element)
            return node;
        node = node->next;
    }
    return NULL;
}

int
clib_container_double_linked_list_remove(struct clib_container_double_linked_list *list, void *element, void **out) {
    struct clib_container_double_linked_list_node *node = get_node(list, element);
    if (!node) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    if (out) {
        *out = node->data;
    }
    unlink_node(list, node);
    return CLIB_RES_OK;
}


int clib_container_double_linked_list_remove_with_index(struct clib_container_double_linked_list *list, size_t index,
                                                        void **out) {
    struct clib_container_double_linked_list_node *node;
    int code = get_node_index(list, index, &node);

    if (code != CLIB_RES_OK) {
        return code;
    }
    if (out) {
        *out = node->data;
    }
    unlink_node(list, node);
    return CLIB_RES_OK;
}

int clib_container_double_linked_list_remove_first(struct clib_container_double_linked_list *list, void **out) {
    if (!list->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    void *e = unlink_node(list, list->head);
    if (out) {
        *out = e;
    }
    return CLIB_RES_OK;
}

int clib_container_double_linked_list_remove_last(struct clib_container_double_linked_list *list, void **out) {
    if (!list->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    void *e = unlink_node(list, list->tail);
    if (out) {
        *out = e;
    }
    return CLIB_RES_OK;
}

int clib_container_double_linked_list_replace_with_index(struct clib_container_double_linked_list *list, void *element,
                                                         size_t index, void **out) {
    struct clib_container_double_linked_list_node *node;
    int code = get_node_index(list, index, &node);
    if (code == CLIB_RES_OK) {
        void *old = node->data;
        node->data = element;
        if (out)
            *out = old;
    }
    return CLIB_RES_OK;
}


int clib_container_double_linked_list_get_first(struct clib_container_double_linked_list *list, void **out) {
    if (list->size == 0) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    *out = list->head->data;
    return CLIB_RES_OK;
}


int clib_container_double_linked_list_get_last(struct clib_container_double_linked_list *list, void **out) {
    if (list->size == 0) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    *out = list->tail->data;
    return CLIB_RES_OK;
}

int clib_container_double_linked_list_get_with_index(struct clib_container_double_linked_list *list, size_t index,
                                                     void **out) {
    struct clib_container_double_linked_list_node *node;
    int code = get_node_index(list, index, &node);
    if (code == CLIB_RES_OK) {
        *out = node->data;
    }
    return code;
}

static void
swap_adjacent(struct clib_container_double_linked_list_node *n1, struct clib_container_double_linked_list_node *n2) {
    if (n1->next == n2) {
        if (n2->next)
            n2->next->prev = n1;

        n1->next = n2->next;

        if (n1->prev)
            n1->prev->next = n2;

        n2->prev = n1->prev;

        n1->prev = n2;
        n2->next = n1;
        return;
    }

    if (n2->next == n1) {
        if (n1->next)
            n1->next->prev = n2;

        n2->next = n1->next;

        if (n2->prev)
            n2->prev->next = n1;

        n1->prev = n2->prev;

        n2->prev = n1;
        n1->next = n2;
        return;
    }
}

static void swap(struct clib_container_double_linked_list_node *n1, struct clib_container_double_linked_list_node *n2) {
    if (n1->next == n2 || n2->next == n1) {
        swap_adjacent(n1, n2);
        return;
    }

    struct clib_container_double_linked_list_node *n1_left = n1->prev;
    struct clib_container_double_linked_list_node *n1_right = n1->next;
    struct clib_container_double_linked_list_node *n2_left = n2->prev;
    struct clib_container_double_linked_list_node *n2_right = n2->next;

    if (n1_left)
        n1_left->next = n2;

    n2->prev = n1_left;

    if (n1_right)
        n1_right->prev = n2;

    n2->next = n1_right;

    if (n2_left)
        n2_left->next = n1;

    n1->prev = n2_left;

    if (n2_right)
        n2_right->prev = n1;

    n1->next = n2_right;
}

void clib_container_double_linked_list_reverse(struct clib_container_double_linked_list *list) {
    if (list->size == 0 || list->size == 1) {
        return;
    }
    struct clib_container_double_linked_list_node *head_old = list->head;
    struct clib_container_double_linked_list_node *tail_old = list->tail;

    struct clib_container_double_linked_list_node *left = list->head;
    struct clib_container_double_linked_list_node *right = list->tail;

    size_t i;
    for (i = 0; i < list->size / 2; i++) {
        struct clib_container_double_linked_list_node *tmpl = left->next;
        struct clib_container_double_linked_list_node *tmpr = right->prev;

        swap(left, right);

        left = tmpl;
        right = tmpr;
    }

    list->head = tail_old;
    list->tail = head_old;
}




